package leetcode.pre50;

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 示例 1:
 * <p>
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 * <p>
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @date 2020/4/24 15:44
 */
public class Code14_LongestCommonPrefix {
    /**
     * 方式1：两两比较。
     * 时间复杂度是O(S)，S为字符串数组中所有字符的总个数。
     * 最坏情况是所有的字符串都相等，要全部遍历。
     */
    public String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String pre = strs[0];
        for (int i = 1; i < strs.length; i++) {
            //当前str[i]与已经形成的pre取 公共前缀
            pre = doCommonPre(pre,strs[i]);
            if(pre.equals(""))return pre;
        }
        return pre;
    }

    /**
     * 方式2：水平扫描。
     * 第一次取所有字符串的第一个字符，第二次取第二个，以此类推。
     * 这样当有一个字符串完毕或者有一个不同，就可以停止扫描。
     * 时间复杂度是O(S)，S为字符串数组中所有字符的总个数。
     * 最坏情况是所有的字符串都相等，要全部遍历。
     */
    public String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (int i = 0; i < strs[0].length(); i++) {
            //扫描第i个字符
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                //退出的条件。 case1 有一个已经被扫描完毕  case2 有一个不等
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);

            }
        }
        return strs[0];
    }

    /**
     * 方式3：分治。思路同归并排序。
     * 复杂度https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode/
     * 时间O(s)
     * 空间O(mlogn)  最坏情况下，我们有 n 个长度为 m 的相同字符串
     * 内存开支主要是递归过程中使用的栈空间所消耗的。
     * 一共会进行 log(n)次递归，每次需要 m 的空间存储返回结果，
     * 所以空间复杂度为 O(mlogn)。
     */
    public String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return process(strs, 0, strs.length - 1);
    }

    private String process(String[] strs, int l, int r) {
        if (l >= r) {
            return strs[l];
        }
        int mid = (l + r) >> 1;
        //左侧规模是前缀
        String leftPre = process(strs, l, mid);
        //右侧规模是前缀
        String rightPre = process(strs, mid + 1, r);
        return doCommonPre(leftPre, rightPre);
    }

    //返回两个字符串的前缀
    private String doCommonPre(String leftPre, String rightPre) {
        int i = 0;
        for (; i < leftPre.length() && i < rightPre.length(); i++) {
            if (leftPre.charAt(i) != rightPre.charAt(i)) break;
        }
        if (i == 0) return "";
        //包括 i == Math.min(len1,len2)情况
        return leftPre.substring(0, i);
    }
}
